//
// Created by Administrator on 2021/12/31.
//

#ifndef CPP_LEARNING_BIN_NODE_HPP
#define CPP_LEARNING_BIN_NODE_HPP
#include <iostream>
#include <queue>
#define BinNodePosi(T) BinNode<T>*                     // 节点位置
#define stature(p) ((p) ? (p)->height : -1)            // 节点高度(空树的高度为-1)
typedef enum {RB_RED, RB_BLACK} RBColor;               // 节点颜色

// BinNode的转态与性质的判断

// 这里的x全部都不是指针
#define IsRoot(x) (!(x).parent)
#define IsLChild(x) (!IsRoot(x) && (&(x) == (x).parent->lc))
#define IsRChild(x) (!IsRoot(x) && (&(x) == (x).parent->rc))
#define HasParent(x) (!IsRoot(x))
#define HasLChild(x) ((x).lc)
#define HasRChild(x) ((x).rc)
#define HasChild(x)  (HasLChild(x) || HasRChild(x))
#define HasBothChild(x) (HasLChild(x) && HasRChild(x))
#define IsLeaf(x)   (!HasChild(x))

#define sibling(p)   (IsLChild(*(p))? (p)->parent->rc : (p)->parent->lc)        //兄弟的指针
#define uncle(p)    (IsLChild(*((p)->parent)) ? (p)->parent->parent->rc : (p)->parent->parent->lc)
#define FromParentTo(x)    ( \
                                    IsRoot(x) ? this->_root : ( \
                                                                IsLChild(x) ? (x).parent->lc : (x).parent-> rc \
                                                         )\
                           )

template <typename T>
struct BinNode;
// 中序遍历
template<typename T,typename VST>
void travIn_I1(BinNodePosi(T) pNode,VST &visit){

}

template<typename T,typename VST>
void travIn_I2(BinNodePosi(T) pNode,VST &visit){

}
template<typename T,typename VST>
void travIn_I3(BinNodePosi(T) pNode,VST &visit){

}
template<typename T,typename VST>
void travIn_I4(BinNodePosi(T) pNode,VST &visit){

}

template<typename T,typename VST>
void travIn_R(BinNodePosi(T) pNode,VST &visit){
    if(pNode == NULL){
        return;
    }
    travIn_R(pNode->lc,visit);
    visit(pNode->data);
    travIn_R(pNode->rc,visit);
}





template <typename T>
struct BinNode{



    T data;

    BinNodePosi(T) parent; BinNodePosi(T) lc; BinNodePosi(T) rc;  // 父 左右节点
    int height;
    int npl;
    RBColor  color;  // 颜色 红黑树

    BinNode():parent(NULL), rc(NULL), lc(NULL), height(0), npl(1), color(RB_RED){}

    BinNode(T e, BinNodePosi(T) p=NULL, BinNodePosi(T) lc=NULL, BinNodePosi(T) rc=NULL, int height=0, int l = 1, RBColor c= RB_RED){
        this->data = e;
        parent = p;
        this->lc = lc;
        this->rc = rc;
        this->height = height;
        npl = l;
        color = c;
    }

    // 操作接口

    // 计算当前节点及其后代的个数
    int size();
    BinNodePosi(T) insertAsLC(T const& e);
    BinNodePosi(T) insertAsRC(T const& e);
    // 中序遍历下的直接后继
    BinNodePosi(T) succ();

    template<typename VST>
    void travLevel( VST&);
    template<typename VST>
    void travPre( VST&);
    template<typename VST>
    void travIn( VST&);
    template<typename VST>
    void travPost( VST&);

    // 比较器 判等器
    bool operator< (BinNode<T> const & bn){
        return data < bn.data;
    }
    bool operator== (BinNode<T> const & bn){
        return data == bn.data;
    }
};
template <typename T>
int BinNode<T>::size(){
    int num = 0;
    if(HasLChild(*this)){
        num += this->lc->size();
    }
    if(HasRChild(*this)){
        num += this->rc->size();
    }
    return num + 1;

}
template <typename T>
BinNodePosi(T) BinNode<T>::succ(){
    // 如果有右节点, 那么后继就是该节点右子树里面的最左的一个
    BinNodePosi(T) succNode;
    if(HasRChild(*this)){
        succNode = this->rc;
        while (HasLChild(*succNode)){
            succNode = succNode->lc;
        }
        return succNode;
    }

    // 把this 包含为其左子树的最小祖父节点
    succNode = this;
    while (HasParent(*succNode) && IsRChild(*succNode)){
        succNode = succNode->parent;
    }
    if(HasParent(*succNode) && IsLChild(*succNode)){
        succNode = succNode->parent;
        return succNode;
    }

    return NULL;
}


template <typename T>
BinNode<T> * BinNode<T>::insertAsLC(const T &e) {
    lc = new BinNode<T>(e, this);
}

template <typename T>
BinNode<T> * BinNode<T>::insertAsRC(const T &e) {
    rc = new BinNode<T>(e, this);
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// 遍历相关

template <typename T>
template<typename VST>
void BinNode<T>::travPost( VST &visit) {

    if(HasLChild(*this)){
        this->lc->travPost(visit);
    }
    if(HasRChild(*this)){
        this->rc->travPost(visit);
    }

    visit(this->data);
}

template <typename T>
template<typename VST>
void BinNode<T>::travIn( VST &visit) {

    if(HasLChild(*this)){
        this->lc->travIn(visit);
    }

    visit(this->data);

    if(HasRChild(*this)){
        this->rc->travIn(visit);
    }


}

// 前序遍历
template <typename T>
template<typename VST>
void BinNode<T>::travPre( VST &visit) {
    visit(this->data);
    if(HasLChild(*this)){
        this->lc->travPre(visit);
    }
    if(HasRChild(*this)){
        this->rc->travPre(visit);
    }
}


// 层次遍历需要借助队列先进先出的特性实现
template <typename T>
template<typename VST>
void BinNode<T>::travLevel( VST &visit) {
    std::queue<BinNodePosi(T)> nodeQueue;
    nodeQueue.push(this);
    while (!nodeQueue.empty()){
        BinNodePosi(T) pNode = nodeQueue.front();
        nodeQueue.pop();
        visit(pNode->data);
        if(HasLChild(*pNode)){
            nodeQueue.push(pNode->lc);
        }
        if(HasRChild(*pNode)){
            nodeQueue.push(pNode->rc);
        }
    }
}



#endif //CPP_LEARNING_BIN_NODE_HPP
